Out: Monday, January 25, 2016
Due: Monday, February 1, 2016 at 500pm EST
The goal of this problem set is to help you design functions that deal with finite data.
You must use the HtDP Beginning Student Language to solve the problems.
For these problems, download a copy of extras.rkt and put it in the folder with your solutions. Then import this library by including the line
(require "extras.rkt")at the top of your file with the other requires. Then, for each problem, put in lines that say
(provide function)for each deliverable function. Thus, for problem 1, the top of your
editor.rkt file should say
(require rackunit) (require 2htdp/universe) ; needed for key=? (require "extras.rkt") (provide make-editor editor-pre editor-post editor? edit)
This will allow our testing framework to import your file and do automated testing on it.
Remember that you must follow the design recipe. Your deliverables include the data definitions (including interpretation and templates), contract and purpose header, code, and tests. Be sure to follow our coding conventions. This will make the TA's job much easier.
Be sure to sync your work and fill
out a Work Session Report at the end of every work session. Use the
Work Session Report for
PS02. Remember to include extras.rkt and any other local
files you need (such as a fsm.jpg or fsm.png
file) in your repository folder.
You are to write a file called editor.rkt
that provides
the following functions:
make-editor editor-pre editor-post editor? edit
Note: for our purposes, we will consider KeyEvent to be a scalar
data type, which can be decomposed using the Cases strategy.
KeyEvent and key=? are defined in the
2htdp/universe module. Look in the Help Desk for details.
You will
need to require 2htdp/universe to import
key=?.
We will be doing automated testing of your solution, so be sure your solution is in the right place (set02/editor.rkt in your private cs5010sp16/pdp-YOURUSERNAME repository), and that it provides all the functions listed above. To see if your file is in the right place, insert the following line somewhere near the top of your file:
(check-location "02" "editor.rkt")
As in Exercise 111,
you are to design a set of functions that illustrate the
workings of a finite-state machine. Your machine will accept
a sequence of letters
(with each letter represented as a 1String)
if and only if that sequence
exactly matches
the regular expression
((a | b)* r (a | c | d)*)*
The empty sequence matches that regular expression, as do the sequences r, arc, bard, and abracadabra, but the sequences a, card, and bcr do not match.
The legal inputs that can be passed as a second argument to your "next-state" function are precisely the strings "a", "b", "c", "d", and "r". Any other inputs violate that function's contract; its behavior on illegal inputs is unspecified.
First perform an information analysis and design the data
representation for the states of your machine.
Your information analysis and design should include a
state-transition diagram (like the ones
here) that shows the meaning of your machine states.
Keep your state transition diagram as simple as possible.
Submit your state-transition diagram either as ascii art in your
fsm.rkt file, or in
JPEG or
PNG
format as a separate file named fsm.jpg or fsm.png,
which you can create using a graphics program or by drawing
your state transition diagram on a piece of paper and taking
a good picture of it.
After you have done your data design, continue using the design recipe to design and provide the following functions in a file named fsm.rkt
initial-state : Number -> State GIVEN: a number RETURNS: a representation of the initial state of your machine. The given number is ignored. next-state : State MachineInput -> State GIVEN: a state of the machine and a machine input RETURNS: the state that should follow the given input. accepting-state? : State -> Boolean GIVEN: a state of the machine RETURNS: true iff the given state is a final (accepting) state rejecting-state? : State -> Boolean GIVEN: a state of the machine RETURNS: true iff there is no path (empty or non-empty) from the given state to an accepting state
Please note that some of your states are likely to be neither accepting nor rejecting.
You will need to provide data definitions for State and for MachineInput. Be sure to write an interpretation for each state. There is no need to write an interpretation for MachineInput, since the problem is already phrased in terms of strings.
Remember that we will be doing automated testing of your solution, so be sure your solution is in the right place (set02/fsm.rkt in your private cs5010sp16/pdp-YOURUSERNAME repository), and that it provides all the functions listed above. To see if your file is in the right place, insert the following line somewhere near the top of your file:
(check-location "02" "fsm.rkt")
Once created and set in motion, the Perpetual Goofball moves forever while its center maintains a perfectly constant speed.
For safety reasons, the Perpetual Goofball's motion is confined to the floor of a specially constructed square arena that measures 4 metres (400 cm) on each side.
The Perpetual Goofball is circular, with a normal radius of 20cm. Whenever the Perpetual Goofball touches any side of the arena, however, its radius automatically contracts to match the distance from the Perpetual Goofball's center to the nearest side of the arena.
The Perpetual Goofball's radius never becomes less than zero. When its radius reaches zero, the Perpetual Goofball rebounds via a perfect bounce.
A perfect bounce is defined as follows. Consider a Cartesian coodinate system in which the x and y axes are parallel to the sides of the arena, and let vx and vy be the Perpetual Goofball's components of velocity in the x and y directions. If its radius reaches zero because it is touching a side of the arena that runs parallel to the y axis, then its velocity in the x direction changes from vx to -vx. If its radius reaches zero because it is touching a side of the arena that runs parallel to the x axis, then its velocity in the y direction changes from vy to -vy.
We will use graphics-style coordinates instead of mathematical coordinates, with the walls of the arena parallel to the x and y axes and the exact center of the arena at the origin. That implies the northernmost wall of the arena is at y = -2m = -200cm and the eastern wall is at x = 2m = 200cm.
You will simulate a prototype of the Perpetual Goofball whose direction of travel is constrained to the following eight directions:
The prototype's velocity is also constrained by requiring each of its vx and vy components to be -1, 0, or +1.
Your job is to write a file called goofball.rkt
that provides the following functions:
goofball-at : Integer Integer Integer Integer -> Goofball
GIVEN: an x-coordinate and a y-coordinate in cm,
and velocity components vx and vy in cm/s
WHERE: the x and y coordinates lie within the bounds of the arena,
and both vx and vy have absolute value less than or equal to 1
RETURNS: a Perpetual Goofball with its center at the x and y coordinates,
velocity components vx and vy, and radius determined by its
distance from the nearest arena wall up to a maximum of 20cm
goofball-radius : Goofball -> Integer
GIVEN: a Goofball
RETURNS: its radius, in cm
goofball-x : Goofball -> Integer
goofball-y : Goofball -> Integer
GIVEN: a Goofball
RETURNS: its corresponding x or y coordinate, in cm
goofball-vx : Goofball -> Integer
goofball-vy : Goofball -> Integer
GIVEN: a Goofball
RETURNS: its corresponding vx or vy velocity component, in cm/s
goofball-one-second-later : Goofball -> Goofball
GIVEN: a Goofball
RETURNS: a Goofball like the given Goofball would become one second later,
following the Goofball's laws of motion (and interaction with the arena)
Note: When a specification uses a single purpose statement to describe
a related group of functions, as was done above with
goofball-x and goofball-y, and with
goofball-vx and goofball-vy,
you need only write down the purpose statement once.
If your design strategy is the same for all of the functions in a group,
then you only have to write that design strategy down once.
Your examples and tests, however, must cover all of the functions.
As before, remember that we will be doing automated testing of your solution, so be sure it is in the right place with the correct file name.
Last modified: Mon Jan 25 2016